\section{Introducci\'on}

Los productores del nuevo reality show La Matrix, nos contrataron para eleborar un algoritmo que, dado un campo de \textbf{nxn} celdas, cada una de ellas con un valor positivo mayor que cero (representando la cantidad de celdas de distancia a las que se puede saltar desde ella), nos permita encontrar el camino con menos saltos desde una celda origen hacia una destino.\\ \\
Deberemos tener en cuenta que:
\begin{itemize}
\item No es posible saltar diagonalmente
\item Disponemos de una cantidad \textbf{k} de ``potencia extra'' que podremos utilizar para aumentar la distancia del salto cuando lo creamos conveniente. 
\end{itemize}
\\
\\
Dicho esto, la entrada del algoritmo ser\'a la siguiente:
\begin{itemize}
\item Un entero \textbf{n} $\rightarrow$ Representar\'a la cantidad de filas y de columnas del campo de juego.
\item $2$ enteros \textbf{fo, co} $\rightarrow$ Representar\'an la posicion origen.
\item $2$ enteros \textbf{fd, cd} $\rightarrow$ Representar\'an la posicion destino.
\item Un entero \textbf{k} $\rightarrow$ Representar\'a las cantidad de unidades de potencia extra de las que disponemos.
\item $n^2$ enteros $\rightarrow$ Representar\'an las unidades de potencia de cada una de las celdas del campo de juego. 
\end{itemize}
\\
\\
La salida de nuestro algoritmo deber\'a ser la siguiente:
\begin{itemize}
\item Un entero \textbf{s}, siendo este la menor cantidad posible de saltos desde el origen hasta la celda destino.
\item \textbf{s} lineas con los siguientes datos:
\begin{itemize}
\item La fila y la columna a la cual se salta.
\item La potencia extra que se uso en este salto (si no se emplea potencia extra ser\'a 0).
\end{itemize}
\end{itemize}


\\
\subsection{Ejemplo}
una instancia valida de el problema:
\\
\\
\begin{tabular}{| l | l |}
\hline
~~~~~~~~~~Entrada\\ \hline
$
\begin{vmatrix}
5 & 4 & 4 & 0 & 0 &  2 \\
1 & 2 & 1 & 3 & 1 \\
3 & 1 & 1 & 2 & 1 \\
1 & 1 & 1 & 1 & 1 \\
2 & 2 & 1 & 1 & 1 \\
2 & 1 & 1 & 1 & 2 \\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\quad \quad
\begin{tabular}{| l | l |}
\hline
Salida\\ \hline
$
\begin{vmatrix}
3  \\
0 & 4 & 2 \\
0 & 3 & 0 \\
0 & 0 & 0 \\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\\ \\ \\
En este caso el camino con menor cantidad de saltos es:
\begin{itemize}
\item Saltar de la posici\'on [4][4] hacia la [0][4] utilizando dos unidades de potencia extra.
\item Saltar de la posici\'on [0][4] hacia la [0][3] utilizando cero unidades de potencia extra.
\item saltar de la posici\'on [0][3] hacia la [0][0] utilizando cero unidades de potencia extra.
\end{itemize}


\section{Idea General de Resoluci\'on}
La idea general del algoritmo ser\'a representar al campo de juego como un grafo, siendo cada casilla un nodo del mismo.
Un nodo \textbf{a} tendr\'a como adyacente a otro nodo \textbf{b} si y solo si la potencia de la celda asociada al nodo \textbf{a} permite saltar hacia la celda representada por el \textbf{b}.
\\
\\
A esta altura, teniendo el grafo ya conectado, si realizamos una busqueda \textbf{bfs} con el nodo origen como raiz, podremos obtener la menor cantidad de saltos hasta el resto de las celdas/nodos, en particular al nodo destino.\\
Pero no estariamos considerando la posibilidad de utilizar potencia extra, deberemos ingeniarnoslas un poco m\'as.\\
\\
Lo que haremos ser\'a lo siguiente:
\begin{itemize}
\item Todas las adyacencias ahora tambi\'en contar\'an con un entero asociado que indicar\'a cuantas unidades de potencia extra se utilizan para llegar.
\item Todas las adyacencias que ya teniamos, las anotaremos como que utilizan 0 unidades de potencia extra.
\item Para todos los nodos haremos lo siguiente\\ 
Sea el nodo \textbf{a} con potencia \textbf{x} y sea \textbf{e} las unidades extra disponibles:
\begin{itemize}
\item Le agregaremos como adyacencia de \textbf{a} todos los nodos que se encuentren a distancia \textbf{g}, con $x < g <= x + e$
\item A estas adyacencias las anotaremos como que utilizan $g-x$ unidades de potencia extra.
\end{itemize}
\end{itemize}
\\
\\
\\
Ahora s\'i, con nuestro nuevo grafo podremos aplicar \textbf{bfs}, pero con algunas variantes:
\begin{itemize}
\item Cada nodo tendr\'a un entero asociado que representar\'a las unidades de potencia extra que le quedan al llegar a este.
\item Cuando anotemos que el nodo \textbf{a} es padre del \textbf{b}, la cantidad de potencia extra que qedar\'a asociada al nodo \textbf{b} se calcular\'a de la siguiente manera:\\
\[
  P_b = P_a - P_a_b
\]
Siendo $P_b$ la potencia asociada al nodo \textbf{b} en el bfs y $P_a$ la del nodo \textbf{a}. Y siendo $P_a_b$ la potencia extra asociada a la adyacencia del nodo \textbf{a} con el \textbf{b}.
\item Un nodo \textbf{a} no podr\'a ser padre de un nodo \textbf{b} si la potencia asociada a la adyacencia del nodo \textbf{a} con el \textbf{b} es mayor que la potencia asociada al nodo \textbf{a} en el bfs.
\end{itemize}



\newpage

\textbf{Nota:} Los enteros i, j y numero de la clase nodo son utilizados para devolver la salida del algoritmo.\\
\indent \indent \indent g es las unidades de potencia extra que nos dan.\\ \\

\subsection{Pseudoc\'odigo}


\begin{algorithm}
\begin{algorithmic}[1]\parskip=1mm
\caption{class Nodo}
	\STATE{\textbf{int} p, distancia, i, j, numero}
	\STATE{\textbf{bool} noVisitado}
	\STATE{\textbf{Nodo*} padre}
	\STATE{\textbf{vector $<$pair$<$Nodo*, int$>$ $>$} adyacentes}
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}[1]\parskip=1mm
\caption{vector$<$vector$<$Nodo*$>$ $>$ crearGrafo(int n, int g)}
  \STATE{\textbf{vector$<$vector$<$Nodo*$>$ $>$} Matrix}
  \STATE{Inicializo Matrix con las celdas del campo de juego}
  \STATE{\textbf{For} cada celda/nodo \textbf{j} de Matrix \textbf{Do:}}
    \STATE{\quad Para cada nodo \textbf{k} alcanzable desde j hacia la derecha con $P_j$ (la potencia inicial de j)}
      \STATE{\quad \quad  Agrego el par (k, 0) al vector de adyacentes de \textbf{j}
    \STATE{\quad Lo mismo para los otros 3 lados}
    \STATE{\quad Para cada nodo \textbf{k} a una distancia \textbf{h} del nodo j hacia la derecha, con $P_j < h \leq P_j+g$}
      \STATE{\quad \quad  Agrego el par (k, h) al vector de adyacentes de \textbf{j}
    \STATE{\quad Lo mismo para los otros 3 lados}
\end{algorithmic}
\end{algorithm}
\\
\\
\begin{algorithm}
\begin{algorithmic}[1]\parskip=1mm
\caption{\textbf{void} bfs(vector$<$vector$<$Nodo*$>$ $>$ matrix, Nodo* origen, int g)}
  \STATE{Todos los nodos est\'an con distancia -1 y como noVisitados desde que los inicializ\'e al comienzo}
  \STATE{Cambio el nodo origen a visitado y con distancia 0}
  \STATE{\textbf{vector$<$pair$<$Nodo*, int$>$ $>$} cola}
  \STATE{Agrego el par (origen, g) a cola} 
  \STATE{\textbf{For} cada nodo \textbf{k} con posici\'on i en cola \textbf{do} }
    \STATE{\quad \textbf{For} cada nodo \textbf{h} con posici\'on j de los adyacentes noVisitados al nodo \textbf{k} \textbf{do}}
      \STATE{\quad \quad \textbf{Si} Si quedan suficiencientes unidades extra para hacer el salto de h a k... \\
      Esto es si (cola[i].second >= adyacentes[j].second)}
        \STATE{\quad \quad \quad Marco h como visitado y con la misma distancia que el nodo k pero incrementada en 1}
        \STATE{\quad \quad \quad Marco k como padre de h}
        \STATE{\quad \quad \quad Agrego el par (h, cola[i].second-adyacentes[j].second) a cola}        
\end{algorithmic}
\end{algorithm}
\\
\\
Para devolver el camino del origen al destino, lo que haremos es ir fijandonos los padres de cada nodo empezando por el nodo destino.


\newpage
\section{Complejidad}
\begin{itemize}
\item Inicializar Matrix tiene una complejidad de $O(n^2)$.
\item La cantidad de adyacencias de cada nodo est\'a acotada por $2*n$ (tendr\'a a lo sumo n-1 adyacencias horizontalmente y otras n-1 verticales).
\item Tenemos $n^2$ nodos con a lo sumo $2*n$ adyacencias cada uno, luego el costo del peor caso para conectar el grafo como queremos ser\'a $O(n^3)$.
\item La complejidad del bfs tambien es $O(n^3)$ ya que para cada nodo recorremos su lista de adyacencias y recorremos todos los nodos.
\item Imprimir la soluci\'on tiene una complejidad de $O(n)$.
\end{itemize}




\section{Correctitud}

Una vez que tenemos el grafo armado, para resolver el problema lo que debemos hacer es buscar el camino m\'inimo desde el nodo origen hasta el nodo destino, BFS es un algoritmo que resuelve este problema eficientemente, lo unico que debemos tener en cuenta es no podemos usar todas los ejes indiscriminadamente, solo podremos utilizar una cantidad limitada de ejes especiales (que haya que utilizar potencia extra para saltar).
\begin{itemize}
\item Si nuestro BFS devuelve un camino que no utiliza m\'as de la cantidad de unidades extra de la que disponemos, el mismo ser\'a una soluci\'on \'optima al problema, ya que BFS garantiza que es el camino de menor cantidad de nodos, es decir, de saltos.

\item Debemos entonces probar que nuestro BFS no se pasa de las unidades extra.\\
Esto podemos ver que se cumple porque cuando estemos iterando el nodo k tenemos un if que chequea dentro de la lista de adyacentes de k que el costo extra del salto de k al nodo adyacente no sea mayor que la cantidad de unidades extra que nos quedan despues de haber llegado al nodo k. 
\\
Empezamos desde el origen con las g unidades extra iniciales y cuando hagamos un salto a un i a un nodo j que utilize x unidades extra, guardaremos que, luego de llegar al nodo j, nos quedan la cantidad de potencia extra que tenia i menos x.   
\end{itemize}

Como nuestro algoritmo nos garantiza que no utilizaremos m\'as de las unidades de potencia extra que disponemos, y bfs nos garantiza que el camino ser\'a el de menor cantidad de saltos. Lo \'unico que nos falta ver es que nuestro grafo esta bien armado.
\\
\\
En nuestro grafo existira un eje normal del nodo i hacia el nodo j, si y solo si, se puede saltar de la celda i hacia la j.\\
Y, existira un eje especial del nodo i hacia el nodo j, si y solo si, se puede saltar de la celda i hacia la j utilizando menos de la cantidad de potencia extra inicial que nos dan, pero al menos utilizando una. Se guardar\'a la cantidad de potencia extra usada sobre ese eje.
\\
\\ 
Esto es una traducci\'on valida del problema, que se traduce a buscar el camino de menor cantidad de nodos desde el nodo Origen hasta el nodo Destino, y que la suma de los pesos de los ejes del camino sea menor que la cantidad de potencia extra que disponemos.














\newpage      
\section{Testing}

\subsection{Una sola celda y Destino==Origen}
\begin{tabular}{| l | l |}
\hline
Entrada \\ \hline
1 0  0 0 0 1 \\ 
5 \\ \hline
\end{tabular}
\quad \quad 
\begin{tabular}{| l | l |}
\hline
Salida \\ \hline
0 \\ \hline
\end{tabular}
\\
\\
Caso borde donde solo hay una celda. A su vez se corresponde con otro caso borde donde la celda Origen es la misma que la Destino. 


\subsection{Sin utilizar potencia extra}

\begin{tabular}{| l | l |}
\hline
Entrada\\ \hline
$
\begin{vmatrix}
5 & 1 & 0 & 4 & 4 & 6 \\
2 & 3 & 1 & 1 & 1 \\
3 & 3 & 2 & 1 & 2 \\
1 & 1 & 1 & 1 & 2 \\
2 & 3 & 5 & 4 & 1 \\
4 & 1 & 1 & 2 & 2 \\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\quad \quad
\begin{tabular}{| l | l |}
\hline
Salida\\ \hline
$
\begin{vmatrix}
2 \\
4 & 0 & 0 \\
4 & 4 & 0 \\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\\
\\
Si bien disponemos de potencia extra, se puede llegar al Destino en la misma cantidad de turnos sin utilizar ninguna.


\subsection{Todas potencias iguales}
\begin{tabular}{| l | l |}
\hline
Entrada\\ \hline
$
\begin{vmatrix}
5 & 1 & 0 & 4 & 4 & 2 \\
2 & 2 & 2 & 2 & 2 \\
2 & 2 & 2 & 2 & 2 \\
2 & 2 & 2 & 2 & 2 \\
2 & 2 & 2 & 2 & 2 \\
2 & 2 & 2 & 2 & 2 \\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\quad \quad
\begin{tabular}{| l | l |}
\hline
Salida\\ \hline
$
\begin{vmatrix}
3 \\
2  & 0  & 0 \\
2  & 4  & 2 \\
4  & 4  & 0  \\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\\
\\
Caso borde donde todas las potencias de los resortes son iguales

\subsection{Un solo salto}


\begin{tabular}{| l | l |}
\hline
Entrada\\ \hline
$
\begin{vmatrix}
5  & 1  & 0  & 1  & 4  & 6 \\
2  & 3  & 1  & 1  & 1 \\
1  & 3  & 2  & 1  & 2 \\
1  & 1  & 1  & 1  & 2 \\
2  & 3  & 5  & 4  & 1 \\
4  & 1  & 1  & 2  & 3 \\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\quad \quad
\begin{tabular}{| l | l |}
\hline
Salida\\ \hline
$
\begin{vmatrix}
1 \\
1  & 4  & 3 \\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\\
\\
Se puede llegar a la salida de un solo salto usando las potencias extra.







\newpage
\section{Resultados}
Para cada n diferente se crearon 10 instancias y se calcul\'o el promedio, a fin de suavizar las curvas obtenidas
\subsection{Diferentes potencias}
En el siguiente gr\'afico se refleja como var\'ia el tiempo de ejecuci\'on con relaci\'on a diferentes intencidades de potencias de los resortes del campo.
\\
\\
\includegraphics[width=16cm]{./SaltosEnLaMatrix/grafico1.png}
\begin{itemize}
\item Potencias Altas $\rightarrow$ Las potencias de los resortes var\'ian aleatoreamente entre $n/2-5$ y $n/2+5$.
\item Potencias Aleatoreas $\rightarrow$ Las potencias var\'ian aleatoreamente entre $1$ y $n/2$.
\item Potencias Bajas $\rightarrow$ Las potencias de los resortes var\'ian aleatoreamente entre $1$ y $7$. 
\item Para los 3 casos la posici\'on de origen y destino es aleatorea y la cantidad de unidades de potencia est\'a fija en 7.
\end{itemize}
\subsection{Variaci\'on para el mismo tamaño}
\\
\includegraphics[width=16cm]{./SaltosEnLaMatrix/grafico2.png}
\begin{itemize}
\item Las posiciones de origen y destino son aleatoreas.
\item Potencias de los resortes del campo var\'ian aleatoreamente entre $1$ y $n/2$.
\item Las unidades de potencia extra var\'ian aleatoreamente entre $0$ y $n/2$.
\end{itemize}
\subsection{Comparaci\'on cota complejidad}
Por \'ultimo, para comparar con la cota de complejidad te\'orica se decidi\'o dividir los valores de tiempo calculados por $n^2$.\\
Con esto esperabamos obtener un gr\'afico de apariencia lineal ya que la complejidad te\'orica era $n^3$\\ \\
Los resultados fueron los siguientes:
\\
\\
\includegraphics[width=16cm]{./SaltosEnLaMatrix/grafico3.png}
\\
Efectivamente como adelantamos, el gr\'afico se asemeja bastante al de una funci\'on lineal.\\ \\
Los valores son los mismos que los de Potencias Aleatoreas del primer grafico


\newpage
\section{Adicionales}
Con las modificaciones que nos dan los productores, nuestro algoritmo tendr\'a la siguiente apariencia:
\begin{itemize}
\item Un nodo \textbf{a} tendr\'a como adyacente a otro nodo \textbf{b} si y solo si la potencia de la celda asociada al nodo \textbf{a} permite saltar hacia la celda representada por el \textbf{b}.\\ El valor asociado a esa adyacencia ya no ser\'a 0, sin\'o que ser\'a $c(a)*d$, siendo \textbf{d} la potencia que se le debe poner al resorte \textbf{a} para llegar a la celda \textbf{b}.
\item La parte de agregar las adyacencias adicionales con las potencias extras que nos daban, ya no la deberemos hacer.
\item Aplicaremos un algoritmo de Dijsktra sobre el grafo y el nodo origen, y obtendremos el camino de peso m\'inimo hasta el destino.
\item Una vez que ya tenemos el camino que gasta la menor cantidad de cr\'editos (de peso m\'inimo), buscaremos entre los resortes que utiliza dicho camino, los que tengan un c(r) mas elevado y utilizaremos todas nuestras unidades de potencia extra sobre estos (sin cambiar la cantidad de potencia que se le da a cada resorte, solo haciendo gratis lo que debiamos pagar antes).
\end{itemize}

La complejidad no se ve afectada, ya que crear las adyacencias nos sigue costando $O(n^3)$ y la complejidad de Dijsktra es $O(n^2)$ (sin colas de prioridad).





